#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
        int n = 0, q = 0;
        cin >> n >> q;
        vector<int> cow(n + 1, 0);
        for(int i = 1; i <= n; i++){
                cin >> cow[i];
        }

        int k = log2(n);
        vector<vector<int>> stmin(n + 1, vector<int>(k + 1, 0)), stmax(stmin);
        for(int i = 1; i <= n; i++){
                stmin[i][0] = cow[i];
                stmax[i][0] = cow[i];
        }

        for(int j = 1; j <= k; j++){
                for(int i = 1; i <= (n - (1 << j) + 1); i++){
                        stmin[i][j] = min(stmin[i][j - 1], stmin[i + (1 << (j - 1))][j - 1]);
                        stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << (j - 1))][j - 1]);
                }
        }

        for(int i = 0, l, r, j, maxhi, minhi; i < q; i++){
                cin >> l >> r;
                // if(l == r){
                //         cout << stmax[l][0] - stmin[l][0] << endl;
                //         continue;
                // }
                j = log2(r - l + 1);
                maxhi = max(stmax[l][j], stmax[r - (1 << j) + 1][j]);
                minhi = min(stmin[l][j], stmin[r - (1 << j) + 1][j]);
                cout << maxhi - minhi << endl;
        }

        return 0;
}